package xyz.scootaloo.oj.offer;

import cn.hutool.core.lang.Console;
import org.junit.Test;
import xyz.scootaloo.oj.ds.TreeNode;

import java.util.*;

/**
 * 未完成
 *
 * @author flutterdash@qq.com
 * @since 2021/4/26 21:48
 */
public class P37 {

    public static class Codec {

        private final StringBuilder cache = new StringBuilder();
        private final Deque<Object> deque = new ArrayDeque<>();
        private final Object NULL_MARK = new Object();
        private final RowInfo row = new RowInfo();
        private final String NULL_STR = "null";

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            return readTreeByRow(root);
        }

        private String readTreeByRow(TreeNode root) {
            if (root == null)
                return "[]";

            clearCache();
            cache.append('[');
            deque.addLast(root);

            while (!deque.isEmpty()) {
                for (int i = 0; i<row.current; i++) {
                    Object obj = deque.removeFirst();
                    if (obj == NULL_MARK) {
                        cache.append(NULL_STR).append(',');
                        continue;
                    }

                    TreeNode node = (TreeNode) obj;
                    cache.append(node.val).append(',');
                    // 除非是当前行节点的最后一个, 否则子节点为空都要做标记
                    if (node.left == null && node.right == null) {
                        if (i >= row.current - 1)
                            continue;
                    }

                    row.next += 2;
                    deque.addLast(node.left == null ? NULL_MARK : node.left);
                    deque.addLast(node.right == null ? NULL_MARK : node.right);
                }

                row.current = row.next;
                row.next = 0;
            }

            return getRes(cache);
        }

        private String getRes(StringBuilder builder) {
            int size = builder.length();
            if (builder.charAt(size - 1) == ',')
                builder.setCharAt(size - 1, ']');
            else
                builder.append(']');
            return builder.toString();
        }

        private void clearCache() {
            this.cache.setLength(0);
            this.deque.clear();
            this.row.clear();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.equals("[]"))
                return null;

            LinkedList<Object> nodes = collectToList(data);
            LinkedList<TreeNode> level = getRootAndRetList(nodes);
            LinkedList<TreeNode> nextLevel = new LinkedList<>();
            LinkedList<TreeNode> tmp;

            TreeNode root = level.getFirst();
            TreeNode node;

            while (!nodes.isEmpty()) {

                row.current = level.size();
                for (int i = 0; i< row.current; i++) {
                    TreeNode curRoot = level.removeFirst();

                    Object obj = nodes.isEmpty() ? NULL_MARK : nodes.removeFirst();
                    if (obj != NULL_MARK) {
                        node = new TreeNode((Integer) obj);
                        curRoot.left = node;
                        nextLevel.add(node);
                    }

                    obj = nodes.isEmpty() ? NULL_MARK : nodes.removeFirst();
                    if (obj != NULL_MARK) {
                        node = new TreeNode((Integer) obj);
                        curRoot.right = node;
                        nextLevel.add(node);
                    }
                }

                tmp = level;
                level = nextLevel;
                nextLevel = tmp;
                nextLevel.clear();
            }

            return root;
        }

        private LinkedList<Object> collectToList(String data) {
            clearCache();
            LinkedList<Object> res = new LinkedList<>();
            int size = data.length();

            for (int i = 1; i<size; i++) {
                char current = data.charAt(i);
                if (current ==',' || current == ']') {
                    String content = cache.toString();
                    if (content.equals(NULL_STR)) {
                        res.add(NULL_MARK);
                    } else {
                        res.add(Integer.parseInt(content));
                    }
                    cache.setLength(0);
                } else {
                    cache.append(current);
                }
            }

            return res;
        }

        private LinkedList<TreeNode> getRootAndRetList(List<Object> nodes) {
            LinkedList<TreeNode> res = new LinkedList<>();
            Object head = nodes.remove(0);
            res.add(new TreeNode((Integer) head));
            return res;
        }

        static class RowInfo {
            private int current;
            private int next;
            void clear() {
                current = 1;
                next = 0;
            }
        }

    }

    Codec codec = new Codec();

    @Test
    public void testInput0() {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        node1.left = node2;
        node1.right = node3;

        node3.left = node4;
        node3.right = node5;

        Console.log(codec.serialize(null));
        Console.log(codec.serialize(node1));
    }

    @Test
    public void testInput1() {
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        node1.right = node2;

        node2.left = node3;
        node2.right = node4;

        node4.right = node5;

        Console.log(codec.serialize(node1));
    }

    @Test
    public void testOutput1() {
        String data = "[1,2,3,null,null,4,5,null,null]";
        TreeNode node = codec.deserialize(data);
        Console.log(node);
    }

    @Test
    public void testOutput2() {
        String data = "[1,null,2,3,4,null,null,null,5]";
        TreeNode node = codec.deserialize(data);
        Console.log(node);
    }

    @Test
    public void testInput3() {
        String data = "[1,6,2,7,5,null,null,8,null,6,4,7,9,null,null," +
                "3,5,null,null,10,8,4,2,null,null,9,11,null,null,1]";
        TreeNode node = codec.deserialize(data);
        Console.log(node);
    }

}
